package com.zhhe.tree;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/*
 *Author:ZouHeng
 *Des:数据结构课程中的二叉查找树
 *Date:2021-01-13  10:52
 */
public class LessonBinarySearchTree<T> {

    /**
     * 记录根节点
     */
    private Node<T> root;

    /**
     * 记录树中的元素个数
     */
    private int size;

    public LessonBinarySearchTree() {
    }

    /**
     * 向树中插入一个键值对
     *
     * @param key
     * @param value
     */
    public void put(Integer key, T value) {
        root = put(root, key, value);
    }

    /**
     * 给指定的树上，添加一个键值对，并返回添加后的新树
     *
     * @param tree
     * @param key
     * @param value
     * @return
     */
    private Node<T> put(Node<T> tree, Integer key, T value) {
        if (tree == null) {
            size++;
            return new Node(null, null, key, value);
        }
        //递归添加结点
        if (key > tree.key) {
            tree.right = put(tree.right, key, value);
        } else if (key < tree.key) {
            tree.left = put(tree.left, key, value);
        } else {
            tree.value = value;
        }
        return tree;
    }

    /**
     * 从树中找到对应的值
     *
     * @param key
     * @return
     */
    public T get(Integer key) {
        return (T) get(root, key);
    }

    private T get(Node<T> node, Integer key) {
        if (node == null) {
            return null;
        }
        if (key > node.key) {
            return (T) get(node.right, key);
        } else if (key < node.key) {
            return (T) get(node.left, key);
        } else {
            return node.value;
        }
    }

    /**
     * 根据key，删除树中的键值对
     * 该方法有问题
     * @param key
     */
    public void delete(Integer key) {
        root = delete(root, key);
    }

    private Node<T> delete(Node<T> tree, Integer key) {
        if (tree == null) {
            return null;
        }
        // 待删除的key大于当前节点的key，继续找当前节点的右子结点
        if (key > tree.key) {
            tree.right = delete(tree.right, key);
        } else if (key < tree.key) {
            tree.left = delete(tree.left, key);
        } else {
            // 待删除的key等于当前节点的key，说明当前结点就是要删除的结点
            // 1. 如果当前结点的右子树不存在，则直接返回当前结点的左子节点
            if (tree.right == null) {
                size--;
                return tree.left;
            }
            // 2. 如果当前结点的左子树不存在，则直接返回当前结点的右子节点
            if (tree.left == null) {
                size--;
                return tree.right;
            }
            // 3. 当前结点的左右子树都存在
            // 3.1 找到右子树中最小的结点
            Node minNode = tree.right;
            // 二叉查找树的左节点一定比右节点小，所以这里只需要遍历左节点
            if (minNode.left != null) {
                minNode = minNode.left;
            }
            // 到这里，就找到了当前节点右子树中最小的节点minNode
            // 3.2 删除右子树中最小的节点
            Node node = tree.right;
            while (node.left != null) {
                if (node.left.left == null) {
                    // 说明n的左节点就是我们要找的最小结点
                    node.left = null;
                } else {
                    node = node.left;
                }
            }
            // 到这里，最小结点已经被删除
            // 3.3 让被删除结点的左子树成为最小结点的左子树。让被删除结点的右子树，成为最小结点的右子树
            minNode.left = tree.left;
            minNode.right = tree.right;
            // 3.4 让被删除结点的父节点指向最小结点
            tree = minNode;
            // 个数-1
            size--;
        }
        return tree;
    }

    /**
     * 查找树中最小的键
     * @return
     */
    public Integer minKey() {
        return minKey(root).key;
    }

    private Node<T> minKey(Node<T> node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node;
        } else {
            return minKey(node.left);
        }
    }

    /**
     * 查找树中最大的键
     * @return
     */
    public Integer maxKey() {
        return maxKey(root).key;
    }

    private Node<T> maxKey(Node<T> node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node;
        } else {
            return maxKey(node.right);
        }
    }

    /**
     * 二叉树的前序遍历
     * @return
     */
    public Queue<T> preOrder() {
        Queue<T> queue = new LinkedList<>();
        preOrder(root, queue);
        return queue;
    }

    private void preOrder(Node<T> node, Queue<T> queue) {
        if (node == null) {
            return;
        }
        queue.add(node.value);
        if (node.left != null) {
            preOrder(node.left, queue);
        }
        if (node.right != null) {
            preOrder(node.right, queue);
        }
    }

    /**
     * 二叉树的中序遍历
     * @return
     */
    public Queue<T> midOrder() {
        Queue<T> queue = new LinkedList<>();
        midOrder(root, queue);
        return queue;
    }

    private void midOrder(Node<T> node, Queue<T> queue) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            // 1.找到当前结点的左子树，如果不为空，递归遍历左子树
            midOrder(node.left, queue);
        }
        queue.add(node.value);
        // 3.找到当前结点的右子树，如果不为空，递归遍历右子树
        if (node.right != null) {
            midOrder(node.right, queue);
        }
    }

    /**
     * 二叉查找树的后序遍历
     * @return
     */
    public Queue<T> afterOrder() {
        Queue<T> queue = new LinkedList<>();
        afterOrder(root, queue);
        return queue;
    }

    private void afterOrder(Node<T> node, Queue<T> queue) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            afterOrder(node.left, queue);
        }
        if (node.right != null) {
            afterOrder(node.right, queue);
        }
        queue.add(node.value);
    }

    /**
     * 二叉树的层序遍历
     * @return
     */
    public Queue<T> layerOrder() {
        //queue用于存储遍历出来的值
        Queue<T> queue = new LinkedList<>();
        //layerQueue用于存储每一层的结点的key
        Queue<Integer> layerQueue = new LinkedList<>();

        layerQueue.add(root.key);
        while (!layerQueue.isEmpty()) {
            Integer key = layerQueue.remove();
            Node<T> currentNode = getNode(root, key);
            queue.add(currentNode.value);
            if (currentNode.left != null) {
                layerQueue.add(currentNode.left.key);
            }
            if (currentNode.right != null) {
                layerQueue.add(currentNode.right.key);
            }
        }

        return queue;
    }

    private Node<T> getNode(Node<T> node, Integer key) {
        if (node == null) {
            return null;
        }
        if (key > node.key) {
            return getNode(node.right, key);
        } else if (key < node.key) {
            return getNode(node.left, key);
        } else {
            return node;
        }
    }

    public int maxDepth() {
        return maxDepth(root);
    }

    private int maxDepth(Node<T> node) {
        if (node == null) {
            return 0;
        }
        // 计算左右子树的最大深度
        int max = 0;
        int leftMax = 0;
        int rightMax = 0;

        if (node.left != null) {
            leftMax = maxDepth(node.left);
        }
        if (node.right != null) {
            rightMax = maxDepth(node.right);
        }

        // 将二者较大的一方赋值给max。当前树的最大深度就是max+1
        max = leftMax > rightMax ? leftMax + 1 : rightMax + 1;
        return max;
    }

    public int size() {
        return size;
    }

    private class Node<T> {
        public Node left;
        public Node right;
        public Integer key;
        public T value;

        public Node(Node left, Node right, Integer key, T value) {
            this.left = left;
            this.right = right;
            this.key = key;
            this.value = value;
        }
    }

    @Test
    public void test() {
//        LessonBinarySearchTree tree = new LessonBinarySearchTree();
//        tree.put(9, "I");
//        tree.put(4, "D");
//        tree.put(2, "B");
//        tree.put(1, "A");
//        tree.put(3, "C");
//        tree.put(7, "G");
//        tree.put(6, "F");
//        tree.put(8, "H");
//        tree.put(5, "E");
//        tree.put(10, "J");
//        System.out.println("树中的最小键：" + tree.minKey());
//        System.out.println("树中的最大键：" + tree.maxKey());
//        System.out.println(tree.get(6));
//        tree.delete(4);
//        System.out.println("树中的元素个数：" + tree.size);

        LessonBinarySearchTree<String> tree = new LessonBinarySearchTree<>();
        tree.put(5, "E");
        tree.put(2, "B");
        tree.put(1, "A");
        tree.put(4, "D");
        tree.put(3, "C");
        tree.put(7, "G");
        tree.put(6, "F");
        tree.put(8, "H");
        //前序遍历顺序EBADCGFH
        Queue<String> preQueue = tree.preOrder();
        System.out.print("前序遍历的顺序：");
        for (String item : preQueue) {
            System.out.print(item);
        }
        System.out.println();
        //中序遍历顺序ABCDEFGH
        Queue<String> midQueue = tree.midOrder();
        System.out.print("中序遍历的顺序：");
        for (String item : midQueue) {
            System.out.print(item);
        }
        System.out.println();
        //后序遍历顺序ACDBFHGE
        Queue<String> afterQueue = tree.afterOrder();
        System.out.print("后序遍历的顺序：");
        for (String item : afterQueue) {
            System.out.print(item);
        }
        System.out.println();
        //层序遍历的顺序EBGADFHC
        Queue<String> layerQueue = tree.layerOrder();
        System.out.print("层序遍历的顺序：");
        for (String item : layerQueue) {
            System.out.print(item);
        }

        System.out.println();
        System.out.println("树的最大深度为：" + tree.maxDepth());
    }

    @Test
    public void testDelete() {
        LessonBinarySearchTree<String> tree = new LessonBinarySearchTree<>();
        tree.put(10, "E");
        tree.put(5, "E");
        tree.put(8, "E");
        tree.put(2, "E");
        tree.put(9, "E");
        tree.delete(5);
        System.out.println();
    }
}
